In current productive application, a main bottleneck of three-dimensional technique such as computer-aided design, reverse engineering, virtual reality, and three-dimensional animation and game is that there is no convenient method for quickly obtaining a three-dimensional model stored in a computer until now. How to start from directly scanning point cloud data to directly obtain a practical point cloud model in a short time is still an unsolved problem. Nowadays, three-dimensional laser scanner is widely used because of its advantage of obtaining three-dimensional surface data of a real object conveniently and flexibly. However, a worldwide difficulty of point cloud data processing is that the point cloud data is generally disheveled with a lot of missing points, noise, and exterior points. After researching for more than 20 years, a technique of rebuilding a three-dimensional model from nearly integrated point cloud data is quite mature. Nevertheless, a linchpin restrains it from becoming a global reverse rebuilding technique is that the point cloud data usually has a large-area missing, and this is a problem that present scan devices cannot solve. Besides, it is difficult to quickly rebuild a satisfied three-dimensional model directly from the point cloud data with missing points using present rebuilding method based on fitting.
A point cloud model generally means a point set of three-dimensional coordinate points on a surface of a scanned object calculated by emitting scan light from a three-dimensional scanner to the surface of the scanned object, and receiving reflected light. Point cloud three-dimensional rebuilding means rebuilding mesh data that can represent an original model based on certain point cloud model data, so as to make computer rendering and user interaction convenient.
In order to better processing point cloud date, extracting a skeleton from the point cloud is a very important pre-processing step. Since the skeleton includes topology structure information of the object, the extracting of the point cloud skeleton can be regarded as an understanding process of the shape of the object. Once the point cloud skeleton is obtained, we can use the skeleton to reverse supplement the missing points and increase the point cloud data, laying a foundation for the following point cloud rebuilding process.
On the other hand, extracting of skeleton information is always an important research subject in computer graphics field. Because, no matter in two-dimensional shapes or in three-dimensional shapes, skeleton is an important describing characteristic to the original data. Skeleton information can greatly help us analyzing and operating all kinds of graphics data, such as shape matching based on the skeleton, skeletal animation and so on.
Extracting a skeleton from a closed three-dimensional grid is quite a mature technique, but extracting a skeleton from a disheveled point cloud is a new problem. The technique of extracting a skeleton from a grid cannot be directly apply in extracting a skeleton from a point cloud because there is a lack of grid connecting information in the point cloud, and the present grid skeleton extracting technique cannot solve the problem of noise, exterior points and missing points in the point cloud. A present solution that can extract a curve skeleton from a point cloud is a method proposed in 2009, called rotational symmetry axis (ROSA). The solution proposed a concept of rotation symmetry axes, and supposed that a basic shape of an inputted model mainly consists of cylinders. Supposing a two-dimensional point set and the normal vector of each point are known, we can calculate a rotation symmetry centre point that can mostly represent the center of the point set. Based on this two-dimensional concept, ROSA solution first finds a best tangent plane of each point in the three-dimensional point cloud, and then projects the inputted points near the tangent plane onto the plane, and calculates the rotation symmetry centre points of the point set on the plane. After contracting the rotation symmetry centre points, and specially processing the junction region, rotational symmetry axis is finally obtained. In addition, it is worthy to be mentioned that there is another document proposed a point cloud skeleton extracting technique based on Laplace contraction. This technique supposes the inputted point cloud data is dense and regular enough, so that a Laplace connecting relation can be built based on the point set, corresponding to building a hidden grid. And then extracts the skeleton with a more mature Laplace grid skeleton extracting technique.
However, the ROSA solution in conventional technique deeply depends on point cloud normal vector information and a hypothesis of the basic shape of the object. In ROSA solution, normal vector information is a prerequisite of calculating local rotation symmetry centre points. Supposing the basic shape as a cylinder is a linchpin of well extracting axis even in missing data. But normal vector information is a value estimated from local neighborhood point information rather than obtained directly from a hardware device. On the situation with a great deal of exterior points and noise, it is easy to estimate wrong normal vector and direction, thus, the accuracy of the ROSA solution for extracting point cloud skeleton in conventional technique is low.